home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / xpaint-2.1.1 / imageComp.c < prev    next >
C/C++ Source or Header  |  1995-05-03  |  14KB  |  551 lines
  1. /* +-------------------------------------------------------------------+ */
  2. /* | Copyright (C) 1993, David Koblas (koblas@netcom.com)              | */
  3. /* |                                                                   | */
  4. /* | Permission to use, copy, modify, and to distribute this software  | */
  5. /* | and its documentation for any purpose is hereby granted without   | */
  6. /* | fee, provided that the above copyright notice appear in all       | */
  7. /* | copies and that both that copyright notice and this permission    | */
  8. /* | notice appear in supporting documentation.  There is no           | */
  9. /* | representations about the suitability of this software for        | */
  10. /* | any purpose.  this software is provided "as is" without express   | */
  11. /* | or implied warranty.                                              | */
  12. /* |                                                                   | */
  13. /* +-------------------------------------------------------------------+ */
  14.  
  15. /* reduce.c:
  16.  *
  17.  * reduce an image's colormap usage to a set number of colors.  this also
  18.  * translates a true color image to a TLA-style image of `n' colors.
  19.  *
  20.  * this uses an algorithm by Paul Heckbert discussed in `Color Image
  21.  * Quantization for Frame Buffer Display,' _Computer Graphics_ 16(3),
  22.  * pp 297-307.  this implementation is based on one discussed in
  23.  * 'A Few Good Colors,' _Computer Language_, Aug. 1990, pp 32-41 by
  24.  * Dave Pomerantz.
  25.  *
  26.  * this function cannot reduce to any number of colors larger than 32768.
  27.  *
  28.  * jim frost 04.18.91
  29.  *
  30.  */
  31.  
  32. /*
  33.  * Copyright 1989, 1990, 1991 Jim Frost
  34.  *
  35.  * Permission to use, copy, modify, distribute, and sell this software
  36.  * and its documentation for any purpose is hereby granted without fee,
  37.  * provided that the above copyright notice appear in all copies and
  38.  * that both that copyright notice and this permission notice appear
  39.  * in supporting documentation.  The author makes no representations
  40.  * about the suitability of this software for any purpose.  It is
  41.  * provided "as is" without express or implied warranty.
  42.  *
  43.  * THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  44.  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN
  45.  * NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  46.  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
  47.  * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  48.  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE
  49.  * USE OR PERFORMANCE OF THIS SOFTWARE.
  50.  */
  51.  
  52. #include <X11/Intrinsic.h>
  53. #include <stdio.h>
  54.  
  55. #ifndef NOSTDHDRS
  56. #include <stdlib.h>
  57. #include <unistd.h>
  58. #endif
  59.  
  60. /*
  61. **  swiped from X11/Xfuncproto.h
  62. **   since qsort() may or may not be defined with a constant sub-function
  63. */
  64. #ifndef _Xconst
  65. #if __STDC__ || defined(__cplusplus) || defined(c_plusplus) || (FUNCPROTO&4)
  66. #define _Xconst const
  67. #else
  68. #define _Xconst
  69. #endif
  70. #endif /* _Xconst */
  71.  
  72. #include "image.h"
  73. #include "hash.h"
  74.  
  75. /*
  76. ** this converts a RGB pixel into a 15-bit true color value
  77. */
  78.  
  79. #define TO_15BITS(r,g,b)    ((r & 0xf8) << 7) | ((g & 0xf8) << 2) | ((b & 0xf8) >> 3)
  80.  
  81. /* 
  82. ** these macros extract color intensities, in the compressed range.
  83. */
  84.  
  85. #define RED_INTENSITY(P)   (((P) & 0x7c00) >> 10)
  86. #define GREEN_INTENSITY(P) (((P) & 0x03e0) >> 5)
  87. #define BLUE_INTENSITY(P)   ((P) & 0x001f)
  88.  
  89. /*
  90. **  These macros exctrat the 0..255 range value from the "true color" version
  91. */
  92. #define RED_VALUE(P)   (((P) & 0x7c00) >> 7)
  93. #define GREEN_VALUE(P) (((P) & 0x03e0) >> 2)
  94. #define BLUE_VALUE(P)  (((P) & 0x001f) << 3)
  95.  
  96. /* this structure defines a color area which is made up of an array of pixel
  97.  * values and a count of the total number of image pixels represented by
  98.  * the area.  color areas are kept in a list sorted by the number of image
  99.  * pixels they represent.
  100.  */
  101.  
  102. typedef struct color_area {
  103.     unsigned short    *pixels;    /* array of pixel values in this area */
  104.     unsigned short     npixels;   /* size of above array */
  105.                   /* predicate func to sort with before * splitting */
  106.     int              (*func)(unsigned short *, unsigned short *);   
  107.     unsigned long      count;     /* # of image pixels we represent */
  108.     struct color_area *prev, *next;
  109. } Area_t;
  110.  
  111. typedef struct {  
  112.     unsigned short    idx; 
  113.     unsigned char    r,g,b; 
  114. } color_t;
  115.  
  116. /* 
  117. ** predicate functions for qsort
  118. **   Generated code as you can see.
  119. */
  120.  
  121. #ifndef __STDC__
  122. #define SORT(ca, cb, cc)                                \
  123.     static int sort/**/ca/**/cb/**/cc(unsigned short *p1, unsigned short *p2)    \
  124.     {                                         \
  125.         unsigned int    R1,R2,G1,G2,B1,B2;                    \
  126.         R1 = RED_INTENSITY(*p1);                        \
  127.         G1 = GREEN_INTENSITY(*p1);                        \
  128.         B1 = BLUE_INTENSITY(*p1);                        \
  129.         R2 = RED_INTENSITY(*p2);                        \
  130.         G2 = GREEN_INTENSITY(*p2);                        \
  131.         B2 = BLUE_INTENSITY(*p2);                        \
  132.         if (ca/**/1 == ca/**/2)                         \
  133.             if (cb/**/1 == cb/**/2)                     \
  134.                 return (cc/**/1 < cc/**/2) ? -1 : 1;            \
  135.             else                                \
  136.                 return (cb/**/1 < cb/**/2) ? -1 : 1;            \
  137.         else                                    \
  138.             return (ca/**/1 < ca/**/2) ? -1 : 1;                \
  139.     }
  140. #else
  141. #define SORT(ca, cb, cc)                                \
  142.     static int sort ## ca ## cb ## cc(unsigned short *p1, unsigned short *p2)    \
  143.     {                                         \
  144.         unsigned int    R1,R2,G1,G2,B1,B2;                    \
  145.         R1 = RED_INTENSITY(*p1);                        \
  146.         G1 = GREEN_INTENSITY(*p1);                        \
  147.         B1 = BLUE_INTENSITY(*p1);                        \
  148.         R2 = RED_INTENSITY(*p2);                        \
  149.         G2 = GREEN_INTENSITY(*p2);                        \
  150.         B2 = BLUE_INTENSITY(*p2);                        \
  151.         if (ca ## 1 == ca ## 2)                         \
  152.             if (cb ## 1 == cb ## 2)                     \
  153.                 return (cc ## 1 < cc ## 2) ? -1 : 1;            \
  154.             else                                \
  155.                 return (cb ## 1 < cb ## 2) ? -1 : 1;            \
  156.         else                                    \
  157.             return (ca ## 1 < ca ## 2) ? -1 : 1;                \
  158.     }
  159. #endif
  160.  
  161. SORT(R,G,B)
  162. SORT(R,B,G)
  163. SORT(G,R,B)
  164. SORT(G,B,R)
  165. SORT(B,G,R)
  166. SORT(B,R,G)
  167.  
  168. #undef SORT
  169.  
  170. /* this does calculations on a color area following a split and inserts
  171.  * the color area in the list of color areas.
  172.  */
  173.  
  174. static void insertColorArea(unsigned long *counts, Area_t **rlargest, Area_t **rsmallest, Area_t *area)
  175. {
  176.     int        i;
  177.     unsigned int    red, green, blue;
  178.     unsigned int    min_red, min_green, min_blue;
  179.     unsigned int    max_red, max_green, max_blue= 0;
  180.     Area_t        *largest, *smallest;
  181.  
  182.     /*
  183.     ** update pixel count for this area and find RGB intensity widths
  184.     */
  185.     min_red   = max_red   = RED_INTENSITY(area->pixels[0]);
  186.     min_green = max_green = GREEN_INTENSITY(area->pixels[0]);
  187.     min_blue  = max_blue  = BLUE_INTENSITY(area->pixels[0]);
  188.  
  189.     area->count= 0;
  190.     for (i = 1; i < area->npixels; i++) {
  191.         area->count += counts[area->pixels[i]];
  192.         red   = RED_INTENSITY(area->pixels[i]);
  193.         green = GREEN_INTENSITY(area->pixels[i]);
  194.         blue  = BLUE_INTENSITY(area->pixels[i]);
  195.  
  196.         if (red < min_red)
  197.             min_red= red;
  198.         if (red > max_red)
  199.             max_red= red;
  200.         if (green < min_green)
  201.             min_green= green;
  202.         if (green > max_green)
  203.             max_green= green;
  204.         if (blue < min_blue)
  205.             min_blue= blue;
  206.         if (blue > max_blue)
  207.             max_blue= blue;
  208.     }
  209.  
  210.     /*
  211.     ** calculate widths and determine which predicate function to use based
  212.     ** on the result
  213.     */
  214.  
  215.     red   = max_red   - min_red;
  216.     green = max_green - min_green;
  217.     blue  = max_blue  - min_blue;
  218.  
  219.     if (red > green)
  220.         if (green > blue)
  221.             area->func= sortRGB;
  222.         else if (red > blue)
  223.             area->func= sortRBG;
  224.         else
  225.             area->func= sortBRG;
  226.     else if (green > blue)
  227.         if (red > blue)
  228.             area->func= sortGRB;
  229.         else
  230.             area->func= sortGBR;
  231.     else
  232.         area->func= sortBGR;
  233.  
  234.     /* insert color area in color area list sorted by number of pixels that
  235.     ** the area represents
  236.     */
  237.  
  238.     largest = *rlargest;
  239.     smallest= *rsmallest;
  240.  
  241.     if (largest == NULL) {
  242.         largest = smallest = area;
  243.         area->prev = area->next = (Area_t *)NULL;
  244.     } else if (area->npixels < 2) {
  245.         /*
  246.         **  if we only have one element, our pixel count is immaterial so we get
  247.         **  stuck on the end of the list.
  248.         */
  249.         smallest->next= area;
  250.         area->prev= smallest;
  251.         area->next= (Area_t *)NULL;
  252.         smallest= area;
  253.     } else {
  254.         /*
  255.         **  insert node into list
  256.         */
  257.         Area_t    *cur;
  258.  
  259.         for (cur = largest; cur != NULL; cur= cur->next) {
  260.             if ((area->count > cur->count) || (cur->npixels < 2)) {
  261.                 area->prev= cur->prev;
  262.                 area->next= cur;
  263.                 cur->prev = area;
  264.                 if (area->prev != NULL)
  265.                     area->prev->next= area;
  266.                 else
  267.                     largest= area;
  268.                 break;
  269.             }
  270.         }
  271.         if (cur == NULL) {
  272.             area->prev= smallest;
  273.             area->next= (Area_t *)NULL;
  274.             smallest->next= area;
  275.             smallest= area;
  276.         }
  277.     }
  278.     *rlargest = largest;
  279.     *rsmallest= smallest;
  280. }
  281.  
  282. /*
  283. **  hash table support functions.
  284. */
  285. static int cmpColor(void *a, void *b)
  286. {
  287.     color_t    *ca = (color_t *)a;
  288.     color_t    *cb = (color_t *)b;
  289.  
  290.     if (ca->r != cb->r)
  291.         return ca->r < cb->r ? -1 : 1;
  292.     if (ca->g != cb->g)
  293.         return ca->g < cb->g ? -1 : 1;
  294.     if (ca->b != cb->b)
  295.         return ca->b < cb->b ? -1 : 1;
  296.     return 0;
  297. }
  298.  
  299. static void freeColor(void *junk)
  300. {
  301.     /*
  302.     **  Don't apply a free function to the hashtable items.
  303.     */
  304. }
  305.  
  306. Image    *ImageCompress(Image *input, int ncolors)
  307. { 
  308.     unsigned long    counts[32768];
  309.     unsigned short    array[XtNumber(counts)];
  310.     unsigned char    *ocp;
  311.     unsigned short    *osp;
  312.     int        x, y, i, count, nuniq;
  313.     int        allocated;
  314.     Area_t        *areas, *largest, *smallest;
  315.     Image        *output;
  316.     void        *htable;
  317.     color_t        *ctable;
  318.     
  319.     /*
  320.     **  make sure we have array space...
  321.     */
  322.     if (ncolors > XtNumber(counts)) 
  323.         ncolors = XtNumber(counts);
  324.  
  325.     /*
  326.     **  Why are we trying to compress a b&w image?
  327.     **    or an image that already fits
  328.     */
  329.     if (input->isBW)
  330.         return input;
  331.     if (input->cmapSize != 0 && input->cmapSize < ncolors) 
  332.         return input;
  333.  
  334.     /*
  335.     **  Creata a histogram of 15-bit color values.
  336.     **    also, save the "real" color values.
  337.     **    or at least enough of them so that we know
  338.     **    that compression is really necessary.
  339.     */
  340.     htable = HashCreate(cmpColor, freeColor, 256);
  341.     ctable = (color_t *)XtCalloc(sizeof(color_t), ncolors + 1);
  342.     nuniq  = 0;
  343.  
  344.     for (i = 0; i < XtNumber(counts); i++)
  345.         counts[i] = 0;
  346.     
  347.     for (y = 0; y < input->height; y++) {
  348.         for (x = 0; x < input->width; x++) {
  349.             unsigned char    *dp;
  350.  
  351.             dp = ImagePixel(input, x, y);
  352.  
  353.             if (nuniq <= ncolors && htable != NULL) {
  354.                 color_t        *cptr = &ctable[nuniq];
  355.                 cptr->r = dp[0];
  356.                 cptr->g = dp[1];
  357.                 cptr->b = dp[2];
  358.                 if (HashFind(htable, dp[0], cptr) == NULL) {
  359.                     cptr->idx = nuniq;
  360.                     HashAdd(htable, dp[0], cptr);
  361.                     nuniq++;
  362.                 }
  363.             }
  364.  
  365.             counts[TO_15BITS(dp[0],dp[1],dp[2])]++;
  366.         }
  367.  
  368.         if (y % 256 == 0)
  369.             StateTimeStep();
  370.     }
  371.  
  372.     if (nuniq <= ncolors) {
  373.         /*
  374.         **  Wow, this has enough colors to fit on the requested colormap
  375.         **    This should be able to renumber (compress) an existing
  376.         **    colormap, rather than creating a new image.
  377.         */
  378.         unsigned short    *osp;
  379.         unsigned char    *ocp;
  380.  
  381.         output = ImageNewCmap(input->width, input->height, nuniq);
  382.         for (y = 0; y < nuniq; y++) 
  383.             ImageSetCmap(output, y, 
  384.                     ctable[y].r, ctable[y].g, ctable[y].b);
  385.         
  386.         osp = (unsigned short *)output->data;
  387.         ocp = output->data;
  388.  
  389.         for (y = 0; y < input->height; y++) {
  390.             for (x = 0; x < input->width; x++, osp++, ocp++) {
  391.                 unsigned char    *dp;
  392.                 color_t        *cptr, col;
  393.  
  394.                 dp = ImagePixel(input, x, y);
  395.  
  396.                 col.r = dp[0];
  397.                 col.g = dp[1];
  398.                 col.b = dp[2];
  399.                 cptr = HashFind(htable, dp[0], &col);
  400.  
  401.                 if (nuniq > 256)
  402.                     *osp = cptr->idx;
  403.                 else
  404.                     *ocp = cptr->idx;
  405.             }
  406.  
  407.             if (y % 256 == 0)
  408.                 StateTimeStep();
  409.         }
  410.  
  411.         output->cmapPacked = True;
  412.  
  413.         HashDestroy(htable);
  414.         XtFree((XtPointer)ctable);
  415.         output->maskData = input->maskData;
  416.         input->maskData  = NULL;
  417.         ImageDelete(input);
  418.         return output;
  419.     }
  420.     HashDestroy(htable);
  421.     XtFree((XtPointer)ctable);
  422.  
  423.     /*
  424.     **  Create an array of 15-bit pixel values that actually occur 
  425.     **   in the image.
  426.     */
  427.     count = 0;
  428.     for (i = 0; i < XtNumber(counts); i++) {
  429.         if (counts[i] != 0)
  430.             array[count++] = i;
  431.     }
  432.  
  433.     /*
  434.     **  Create the color areas an initalize the first element
  435.     */
  436.     areas = (Area_t *)XtCalloc(sizeof(Area_t), ncolors);
  437.     areas[0].pixels  = array;
  438.     areas[0].npixels = count;
  439.  
  440.     largest = smallest = NULL;
  441.     insertColorArea(counts, &largest, &smallest, areas);
  442.  
  443.     allocated = 1;
  444.  
  445.     /*
  446.     **  While there are area's still to be broken down 
  447.     **    or the largest cannot be subdivided.
  448.     */
  449.     while (allocated < ncolors && largest->npixels >= 2) {
  450.         Area_t    *newArea, *oldArea;
  451.         int    i, midpoint;
  452.  
  453.         qsort(largest->pixels, largest->npixels, sizeof(short),     
  454.                 (int (*)(_Xconst void *,_Xconst void *))largest->func);
  455.  
  456.         /*
  457.         **  Find the midpoint of the largest area an split
  458.         */
  459.         midpoint = largest->count / 2;
  460.         for (i = 0, count = 0; i < largest->npixels && count < midpoint; i++) 
  461.             count += counts[largest->pixels[i]];
  462.  
  463.         if (i == largest->npixels)
  464.             i--;
  465.         if (i == 0)
  466.             i = 1;
  467.         newArea = areas + allocated;
  468.         newArea->pixels = largest->pixels + i;
  469.         newArea->npixels = largest->npixels - i;
  470.         largest->npixels = i;
  471.         oldArea = largest;
  472.         largest = largest->next;
  473.         if (largest != NULL) 
  474.             largest->prev = NULL;
  475.         else
  476.             smallest = NULL;
  477.  
  478.         /* 
  479.         **  recalculate for each area of split and insert in the area list
  480.         */
  481.         insertColorArea(counts, &largest, &smallest, newArea);
  482.         insertColorArea(counts, &largest, &smallest, oldArea);
  483.  
  484.         allocated++;
  485.  
  486.         if (allocated % 64 == 0)
  487.             StateTimeStep();
  488.     }
  489.  
  490.     output = ImageNewCmap(input->width, input->height, allocated);
  491.     output->maskData = input->maskData;
  492.     input->maskData  = NULL;
  493.  
  494.     for (i = 0; i < allocated; i++) {
  495.         long    red, green, blue;
  496.         int    j;
  497.  
  498.         /* 
  499.         ** calculate RGB table from each color area.  this should really calculate
  500.         ** a new color by weighting the intensities by the number of pixels, but
  501.         ** it's a pain to scale so this just averages all the intensities.  it
  502.         ** works pretty well regardless.
  503.         */
  504.         red = green = blue = 0;
  505.         for (j = 0; j < areas[i].npixels; j++) {
  506.             unsigned short    pixel = areas[i].pixels[j];
  507.  
  508.             red   += RED_VALUE(pixel)   & 0xff;
  509.             green += GREEN_VALUE(pixel) & 0xff;
  510.             blue  += BLUE_VALUE(pixel)  & 0xff;
  511.  
  512.             counts[pixel] = i;
  513.         }
  514.         red   /= areas[i].npixels;
  515.         green /= areas[i].npixels;
  516.         blue  /= areas[i].npixels;
  517.  
  518.         ImageSetCmap(output, i, red, green, blue);
  519.     }
  520.  
  521.     /*
  522.     **  Done with the areas information.
  523.     */
  524.     XtFree((XtPointer)areas);
  525.  
  526.     /*
  527.     **  Copy input to output
  528.     */
  529.  
  530.     ocp = output->data;
  531.     osp = (unsigned short *)output->data;
  532.  
  533.     for (y = 0; y < input->height; y++) {
  534.         for (x = 0; x < input->width; x++) {
  535.             unsigned char    *dp;
  536.  
  537.             dp = ImagePixel(input, x, y);
  538.  
  539.             if (output->cmapSize > 256) {
  540.                 *osp++ = counts[TO_15BITS(dp[0],dp[1],dp[2])];
  541.             } else {
  542.                 *ocp++ = counts[TO_15BITS(dp[0],dp[1],dp[2])];
  543.             }
  544.         }
  545.     }
  546.  
  547.     output->cmapPacked = True;
  548.     ImageDelete(input);
  549.     return output;
  550. }
  551.